\documentclass[a4paper,10pt]{article}
\usepackage[spanish]{babel} % Para división en sílabas español.
\usepackage[utf8]{inputenc} % Para poner acentos.
\usepackage{graphicx} % Paquete para ingresar gráficos
\usepackage{hyperref}
\usepackage{fancybox}

%Encabezado y Pié de página
\input{EncabezadoYPie/EncabezadoyPie.tex}
%Carátula del Trabajo
\title{ \input{Portada/Portada.tex} }

\begin{document}
	\maketitle %Hace que el título anterior sea el principal del documento
	\newpage

	\tableofcontents %Esta línea genera un indice a partir de las secciones y subsecciones creadas en el documento
	\newpage

	\section{Objetivos}
		El objetivo del presente trabajo consiste en familiarizarnos con el conjunto de instrucciones MIPS y el concepto de ABI, 
		modificando un programa realizado previamente a la presente entrega.
		\vspace{1cm}
 	\section{Introducción Teórica}
		\label{sec:InfoTeo}
		Para cumplir con los objetivos de esta entrega se deberá implementar el algoritmo de ordenamiento \emph{mergesort} en assembly de MIPS32. A continuación se explicarán brevemente los conceptos más importantes del ABI utilizado y el conjunto de instrucciones necesarios para desarrollar el trabajo:
		\vspace{0.5cm}
		\subsection{MIPS}
			La arquitectura MIPS presenta 32 registros de propósito general (de 32 bits). Además presenta dos registros especiales para mantener los resultados provenientes de una multiplicación o división y un coprocesador que agrega otros 32 registros de punto flotante (también de 32 bits).
		\vspace{0.5cm}

		\subsection{ABI}
			 Se presentan aquellas consideraciones utilizadas en la presente entrega, sin hacer detalle de otros aspectos que fueron irrelevantes a la hora de realizar la misma.
			\begin{itemize}
			
			\item Los registros \emph{ra, sp, fp, gp, s0, s1..s7}, y \emph{f20..f30} deben ser guardados por la función llamada en caso de que ésta los modifique. 
			
			\item Cada función crea siempre su \emph{stack frame} (pila de llamadas), la cual se compone de áreas de tamaño multiplo de 8 bytes y alineadas a 8 bytes, agregando el \emph{padding} necesario cuando así se requiera.

			\item El \emph{stack frame} posee una cantidad variable de áreas, pero siempre debe incluir una de registros salvados (\emph{saved Regs. Area}). Otras posibles áreas son: la de registros de punto flotante (\emph{Floats Regs. Area}), la de variables locales (\emph{Local and Temporary Variables Area}) y la de argumentos (\emph{Arg Building Area}).
			
			\item En \emph{saved Regs. Area} deben guardarse siempre \emph{fp} (puntero del frame) y \emph{gp} (puntero global y de contexto). Para el caso de una función que no es hoja, debe guardarse \emph{ra} (dirección de retorno). Además, si cualquiera de los registros \$16..\$23 o \$29..\$31 son modificados dentro de la función llamada, deben ser salvados antes de su uso y restaurado antes del retorno a la función que llama.
			
			\item En \emph{Floating-Point Registers Save Area} deben salvarse los registros \emph{f20} a \emph{f30} en el caso de que sean utilizados, teniendo en cuenta las mismas consideraciones que en el punto anterior.
			
			\item El \emph{Arg Building Area} se crea cuando la función no es hoja, posee al menos 16 bytes aún cuando los argumentos de la función llamada sean menos. Cuando los primeros cuatro argumentos son punteros o enteros se pasan en a0 a a3 y son almacenados en ésta área por la función llamada.
			
			\item Los registros son salvados en orden numérico, es decir que los registros numerados más alto se guardan en posiciones más altas de la memoria.

			\end{itemize}
	
		\subsection{Instrucciones}
			\begin{itemize}			
			\item\textbf{Aritméticas}
			\newline
			\newline
			\textbf{Suma:} add \$1, \$2, \$3 (suma \$2 con \$3  y almacena en \$1)
			\newline			
			\newline
			\textbf{Suma sin signo:} addu \$1, \$2, \$3 (suma dos registros sin signo)
			\newline
			\newline
			\textbf{Resta:} sub \$1, \$2, \$3 (resta \$2 con \$3  y almacena en \$1)
			\newline
			\newline
			\textbf{Resta sin signo:} subu \$1, \$2, \$3 (resta dos registros sin signo (\$2 con \$3)  y almacena en \$1)
			\newline
			\newline
			\textbf{Suma inmediata:} addi \$1, \$2, CONST (suma \$2 con CONST  y almacena en \$1)
			\newline	
			\newline
			\textbf{Multiplicación:} mul \$1, \$2 (multiplica dos registros y guarda el resultado de 64 bits en dos registros especiales de la memoria (LO para la parte menos significativa y HI para la más significativa)
			\newline
			\newline
			\textbf{División:} div \$1, \$2 (divide \$1 en \$2, guardando el cociente en LO y el resto en HI)

			\item\textbf{Load/Store}
			\newline
			\newline
			\textbf{Carga de dirección:} la \$1, etiqueta (carga la direccion de memoria de una etiqueta en el registro \$1)
			\newline
			\newline
			\textbf{Carga de palabra:} lw \$1,CONST(\$1) (carga la palabra almacenada desde \$2 + CONST (4 bytes) en el registro \$1)
			\newline
			\newline
			\textbf{Carga de media palabra:} lh \$1,CONST(\$2) (carga la media palabra almacenada desde \$2 + CONST (2 bytes) en el registro \$1)
			\newline
			\newline
			\textbf{Carga de byte:} lb \$1,CONST(\$2) (carga el byte almacenado en \$2 + CONST en el registro \$1)
			\newline
			\newline
			\textbf{Almacenamiento de palabra:} sw \$1,CONST(\$2) (almacena la palabra que se encuentra en el registro \$1  en la dirección \$2 + CONST (4 bytes))
			\newline
			\newline
			\textbf{Almacenamiento de media palabra:} sh \$1,CONST(\$2) (almacena la media palabra que se encuentra en el registro \$1  en la dirección \$2 + CONST (2 bytes))
			\newline
			\newline
			\textbf{Almacenamiento de byte:} sb \$1,CONST(\$2) (almacena el byte cargado en el registro \$1  en la dirección \$2 + CONST )
			\newline
			\newline
			\textbf{Carga del inmediato superior:} lui \$1,CONST  (carga un operando inmediato de 16 bits en los 16 bits del registro especificado.
			\newline
			\newline																						
			\textbf{Mover desde "high"(HI):} mfhi \$1 (mueve un valor de HI al registro)
			\newline
			\newline
			\textbf{Mover desde "low"(LO):} mflo \$1 (mueve un valor de LO al registro)
			\newline
			\newline
			\textbf{Mover :} move \$1, \$2 (mueve el contenido del registro \$2 al registro \$1)
			\newline
			\item\textbf{Lógicas}
			\newline
			\newline
			\textbf{And:} and \$1,\$2,\$3 (hace un And bit a bit entre los registros \$2 y \$3 almacendo el resultado en \$1)
			\newline
			\newline
			\textbf{And con inmediato:} andi \$1,\$2,CONST (hace un And bit a bit entre los registros \$2 y el valor binario de CONST almacendo el resultado en \$1)
			\newline
			\newline
			\textbf{Or:} or \$1,\$2,\$3 (hace un Or bit a bit entre los registros \$2 y \$3 almacendo el resultado en \$1)
			\newline
			\newline
			\textbf{Or con inmediato:} ori \$1,\$2,CONST (hace un Or bit a bit entre los registros \$2 y el valor binario de CONST almacendo el resultado en \$1)
			\newline
			\newline
			\textbf{Or exclusivo:} xor \$1,\$2,\$3 (hace un Xor bit a bit entre los registros \$2 y \$3 almacendo el resultado en \$1)
			\newline
			\newline
			\textbf{Nor:} nor \$1,\$2,\$3 (hace un Or bit a bit entre los registros \$2 y \$3 e invierte el resultado almacenándolo en \$1)
			\newline
			\newline
			\textbf{Inicializar si menor que:} slt \$1,\$2,\$3 (comprueba si el registro \$2 es menor a \$3, almacendo el resultado en \$1) 
			\newline
			\newline
			\textbf{Inicializar si menor que con inmediato:} slti \$1,\$2,CONST (comprueba si un registro es menor que una constante almacendo el resultado en \$1)

			\item\textbf{Desplazamiento de datos}
			\newline
			\newline
			\textbf{Desplazamiento lógico a la izquierda:} sll \$1,\$2,CONST (desplaza el registro \$2 CONST bits a la izquierda guardando el resultado en \$1)
			\newline
			\newline
			\textbf{Desplazamiento lógico a la derecha:} srl \$1,\$2,CONST (desplaza el registro \$2 CONST bits a la derecha, rellenado con ceros, guardando el resultado en \$1)
			\newline
			\newline
			\textbf{Desplazamiento aritmético a la derecha:} sra \$1,\$2,CONST (desplaza el registro \$2 CONST bits rellenando con el bit de signo correspondiente, guardando el resultado en \$1)
  			\newline
			\newline

			\item\textbf{Saltos condicionales}
			\newline
			\newline
			\textbf{Salto si igual:} beq \$1,\$2,CONST (salta a la instrucción situada en la dirección especificada si ambos registros son iguales)
			\newline
			\newline
			\textbf{Salto si no igual:} bne \$1,\$2,CONST (salta a la instrucción situada en la dirección especificada si ambos registros no son iguales)
			\newline
			\newline

			\item\textbf{Saltos incondicionales}
			\textbf{Salto:} j CONST (salta de forma incondicional a la instrucción almacenada en la dirección especificada)
			\newline
			\newline
			\textbf{Salto a registro:} jr \$1 (salta a la dirección almacenada en el registro especificado)
			\newline
			\newline
			\textbf{Salto y enlace:}	jal CONST (salta a la dirección almacenada en el registro especificado, guardando en \$31 la dirección de retorno, a la que se vuelve con jr \$31)
			\newline
			\newline
			\item\textbf{Punto flotante (coprocesador)}
			\newline
			\newline
 			\textbf{Carga: }l.s \$1, CONST (lee de la dirección CONST de memoria un real y lo almacena en \$1)
			\newline
			\newline
 			\textbf{Almacenamiento: }s.s \$1, CONST (escribe en la dirección CONST de memoria el real contenido en \$1)
			\newline
			\newline
 			\textbf{Suma: }	add.s \$1, \$2, \$3 (suma los registros \$2 y \$3 y guarda el resultado en \$1)
			\newline
			\newline
 			\textbf{Resta: }	sub.s \$1, \$2,\$3 (resta los registros \$2 y \$3 y guarda el resultado en \$1)
			\newline
			\newline
 			\textbf{Multiplicación: }	mul.s \$1, \$2, \$3 (multiplica los registros \$2 y \$3 y guarda el resultado en \$1)
			\newline
			\newline
 			\textbf{División: }	div.s \$1, \$2, \$3 (divide los registros \$2 y \$3 y guarda el resultado en \$1)
			\newline
			\newline
 			\textbf{Conversión entero a simple precisión:} cvt.s.w \$1,\$2 (convierte un número entero del registro \$2 a un número de preción simple y lo guarda en \$1)
			\newline
			\newline
			\textbf{Transferencia de Cpu al coprocesador de f.p.: } mtc1 \$1,\$2 (transfiere el registro \$2 de la CPU al registro \$1 del coprocesador de punto flotante)
			\newline
			\newline
			\end{itemize}
			
		\subsection{Directivas}
			Se explica brevemente el significado de las directivas utilizadas en ésta entrega.
			\begin{itemize}
			\item\textbf{.text dirección: }comienza la sección de texto de usuario en la dirección dada.
			\newline
			\item\textbf{.align N: }especifica un alineamiento para la siguiente directiva de datos. N especifica el alineamiento, y debe ser una potencia de 2.
			\newline
			\item\textbf{.globl Simb: }indica que el símbolo es exportado (lo inserta en la tabla de símbolos exportados).
			\newline
			\item\textbf{.extern Simb,t: }indica que el símbolo es importado y ocupa t octetos. Al tiempo, inserta lo inserta en la tabla de símbolos. Cada vez que un símbolo externo aparece en el programa se registra en la tabla de
símbolos importados.
			\newline
			\item\textbf{.ent etiqueta: }marca el comienzo de una subrutina.
			\newline
			\item\textbf{.end etiqueta: }marca el final de una subrutina.
			\newline
			\item\textbf{.set noreorder: }marca el inicio de una región del fichero fuente en la cual el ensamblador no reordena las instrucciones del programa.
			\newline
			\item\textbf{.set reorder: }marca el final de una región de no reordenación. A partir de ella, el ensamblador puede reordenar las instrucciones para mejorar la eficiencia del programa.
			\newline
			\item\textbf{.cpload registro: } toma un registro como argumento, el cual contiene la dirección de la función.
			\end{itemize}

		
			

	\section{Instrucciones para compilar}
			Para compilar el código se debe ejecutar el siguiente comando:
			\begin{verbatim}
					gcc -Wall -o tp1 main.S mergesort.S mergebuffers.S mymalloc.S io.S
			 \end{verbatim}
                        Para facilitar la tarea se incluye un makefile en la versión digital de este trabajo práctico.
			\vspace{0.5cm}
					
	\section{Desarrollo}
		A partir de los conceptos teóricos desarrollados en la sección anterior (\ref{sec:InfoTeo}), se procedió a crear los módulos en \emph{mips32 assembly}. 
		
		\vspace{0.5cm}
		\subsection{Modo de Operación}
			La aplicación desarrollada debe recibir la entrada de caracteres por stdin, y envía la salida (arreglo de bytes ordenados) a stdout.
			\newline
			\vspace{0.5cm}
		
		
		\subsection{Ejemplos}
                Si quisieramos ordenar los bytes del archivo ``desordenado.txt'', podemos ejecutar
             \begin{verbatim}
                ./tp1 < desordenado.txt > ordenado.txt
             \end{verbatim}
             Esto ordena el arreglo de bytes del archivo de entrada, crea el archivo ``ordenado.txt'' y almacena en él el arreglo ordenado. 
	    Si se está ordenando un archivo binario, es recomendable especificar un archivo de salida, como en este caso, y 
	    luego, para visualizar el contenido del archivo binario en formato hexadecimal y separado en bytes, ejecutar el 
	    siguiente comando:
             \begin{verbatim}
                hexdump -C ordenado.txt
             \end{verbatim}
	      En el caso de que el arreglo a ordenar estuviese compuesto por caracteres imprimibles, puede omitirse indicarle un archivo a la salida estándar y ver el resultaddirectamente por consola. De cualquier manera, si se especifica un archivo, este puede verse con cualquier editor 
	      de texto, o por consola con el comando
             \begin{verbatim}
                cat ordenado.txt
             \end{verbatim}
		     
	\section{Implementación}
	  \subsection{Código Fuente main.S}
\begin{scriptsize}
\begin{Verbatim}
#include <mips/regdef.h>
#include <sys/syscall.h>
#define stdinfd 	0
#define stdoutfd 	1



#define LOAD_DATA_SS 48
#define LOAD_DATA_O_ARG (LOAD_DATA_SS)
#define LOAD_DATA_O_RA 40
#define LOAD_DATA_O_FP 36
#define LOAD_DATA_O_GP 32
#define LOAD_DATA_LTA_BYTES_TOTALES	28
#define LOAD_DATA_LTA_NUM_BUFFERS	24
#define LOAD_DATA_LTA_OFFSET		20
#define LOAD_DATA_LTA_BUFFER		16
#define TAM_BUFFER 64
.text
.align 	2
.globl	load_data
.ent	load_data
load_data:
	.frame $fp, LOAD_DATA_SS, ra
	.set  noreorder
   	.cpload  t9
   	.set  reorder

	subu	sp, sp, LOAD_DATA_SS
	sw	ra, LOAD_DATA_O_RA(sp)
	sw	$fp, LOAD_DATA_O_FP(sp)
	sw	gp, LOAD_DATA_O_GP(sp)
	move	$fp, sp
	sw	a0, LOAD_DATA_O_ARG(sp)	# guardo el argumento en el ABA del caller

	# inicializo todas las variables a 0
	sw	zero,LOAD_DATA_LTA_BYTES_TOTALES(sp)
	sw	zero,LOAD_DATA_LTA_OFFSET(sp)	
	sw	zero,LOAD_DATA_LTA_BUFFER(sp)

	# creo un buffer de tamanio TAM_BUFFER
	li	a0, TAM_BUFFER

	la	t9, mymalloc
	jalr	t9
	beqz	v0, return_load_data
	sw	v0, LOAD_DATA_LTA_BUFFER(sp)
	li	t0, 1
	sw	t0, LOAD_DATA_LTA_NUM_BUFFERS(sp)
loop:
	# leo de stdin
	li	a0, stdinfd
	lw	t0, LOAD_DATA_LTA_OFFSET(sp)
	lw	t1, LOAD_DATA_LTA_BUFFER(sp)
	addu	a1, t0, t1
	li	a2, TAM_BUFFER
	la	t9, my_read
	jalr 	t9
	bltz	v0, error
	# actualizo los bytes leidos
	lw	t2, LOAD_DATA_LTA_BYTES_TOTALES(sp)
	addu	t2, v0, t2
	sw	t2,LOAD_DATA_LTA_BYTES_TOTALES(sp)

	bltu	v0, TAM_BUFFER, return_load_data

	# actualizo el numero de buffers
	lw	t3, LOAD_DATA_LTA_NUM_BUFFERS(sp)
	addiu	t3, 1
	sw	t3, LOAD_DATA_LTA_NUM_BUFFERS(sp)

	# llamo a realloc para agrandar el buffer
	lw	a0, LOAD_DATA_LTA_BUFFER(sp)
	mul	a1, t3, TAM_BUFFER
	la	t9, myrealloc
	jalr	t9
	beqz	v0, error
	
	# guardo el nuevo buffer
	sw	v0, LOAD_DATA_LTA_BUFFER(sp)

	# actualizo el offset
	lw	t0, LOAD_DATA_LTA_OFFSET(sp)
	addiu	t0, TAM_BUFFER
	sw	t0, LOAD_DATA_LTA_OFFSET(sp)
	
	b	loop

error:
	# libero la memoria alocada para el buffer
	lw	a0, LOAD_DATA_LTA_BUFFER(sp)
	la	t9, myfree
	jalr	t9

	#cargo el valor de retorno
	li	v0, -1
	b	unwinding_load_data

return_load_data:
	#cargo el valor de retorno
	lw	v0, LOAD_DATA_LTA_BYTES_TOTALES(sp)
	lw	t0, LOAD_DATA_LTA_BUFFER(sp)
	sw	t0, LOAD_DATA_O_ARG(sp)

unwinding_load_data:
	move	sp, $fp
	lw	ra, LOAD_DATA_O_RA(sp)
	lw	$fp, LOAD_DATA_O_FP(sp)	
	addiu	sp, sp, LOAD_DATA_SS
	jr	ra		

.end load_data	

# int main (int argc, char** argv)
#define MAIN_SS	40
#define MAIN_O_ARG (MAIN_SS)
#define MAIN_O_RA 		32
#define MAIN_O_FP 		28
#define MAIN_O_GP 		24
#define MAIN_LTA_BUFFER_SIZE	20
#define MAIN_LTA_BUFFER_PTR	16

.globl	main
.ent	main
main:
	.frame $fp, MAIN_SS, ra
	.set  noreorder
   	.cpload  t9
   	.set  reorder

	subu	sp, sp, MAIN_SS
	sw	ra, MAIN_O_RA(sp)
	sw	$fp, MAIN_O_FP(sp)
	sw	gp, MAIN_O_GP(sp)
	move	$fp, sp
	sw	a0, MAIN_O_ARG(sp)	# guardo el argumento en el ABA del caller
	sw	a1, MAIN_O_ARG+4(sp)
	
	lw	a0, MAIN_LTA_BUFFER_PTR(sp)
	la	t9, load_data	
	jalr	t9
	
	blez	v0, m_error
	sw	v0, MAIN_LTA_BUFFER_SIZE(sp)
	lw	t0, 0(sp)
	sw	t0, MAIN_LTA_BUFFER_PTR(sp)
	
	move 	a1, v0
	move 	a0, t0
	la	t9, merge_sort
	jalr	t9

	beqz	v0, msort_error
	lw	a1, 0(sp)
	lw	a2, MAIN_LTA_BUFFER_SIZE(sp)
	
	li	a0, stdoutfd
	la	t9, my_write
	jalr 	t9

	lw 	a0, MAIN_LTA_BUFFER_PTR(sp)
	la	t9, myfree
	jalr	t9
	b 	return_main

m_error:
	li	v0, -1
	b	unwinding_main

msort_error:
	lw	a0, MAIN_LTA_BUFFER_PTR(sp)
	la	t9, myfree
	jalr	t9
	li	v0, -1
	b	unwinding_main

return_main:
	li	v0, 0

unwinding_main:
	move	sp, $fp
	lw	ra, MAIN_O_RA(sp)
	lw	$fp, MAIN_O_FP(sp)	
	addiu	sp, sp, MAIN_SS
	jr	ra	
	

.end main
\end{Verbatim}
\end{scriptsize}
	\subsection{Código Fuente io.S}
\begin{scriptsize}
\begin{Verbatim}
#include <mips/regdef.h>
#include <sys/syscall.h>

#ifndef 	fp
#define	fp	$fp
#endif

#define SSIZE			(32)

#define	O_RA			(24)
#define	O_FP			(20)
#define	O_GP			(16)

#define 	O_ARG0		(SSIZE)
#define 	O_ARG1		((SSIZE) + 4)
#define 	O_ARG2		((SSIZE) + 8)
#define 	O_ARG3		((SSIZE)	+ 12)

	/* ssize_t	my_read(int,void*,size_t)	*/
	.text
	.align 	2
	.globl	my_read
	.ent		my_read

my_read:
   	.frame fp,32, ra
   	.set  noreorder
   	.cpload  t9  
   	.set  reorder     
	
		subu	sp,sp,SSIZE

		sw		gp,O_GP(sp)
		sw		fp,O_FP(sp)
		sw		ra,O_RA(sp) 
		
		move	fp,sp

		sw		a0,O_ARG0(fp)
		sw		a1,O_ARG1(fp)
		sw		a2,O_ARG2(fp)
		


		li		v0,SYS_read

		lw		a0,O_ARG0(fp)
		lw		a1,O_ARG1(fp)
		lw		a2,O_ARG2(fp)

		syscall

		bne	a3,zero,read_error

		b		read_unwind

read_error:
		li		v0,-1

read_unwind:
		lw		gp,O_GP(sp)
		lw		fp,O_FP(sp)
		lw		ra,O_RA(sp) 
		addiu		sp, sp, SSIZE
		jr		ra
		
		.end		my_read

		/* ssize_t	my_write(int,const void*,size_t)	*/
		.text
		.align 	2
		.globl	my_write
		.ent		my_write

my_write:
   	.frame fp,32, ra
   	.set  noreorder
   	.cpload  t9  
   	.set  reorder     

		subu	sp,sp,SSIZE

		sw		gp,O_GP(sp)
		sw		fp,O_FP(sp)
		sw		ra,O_RA(sp) 
		
		move	fp,sp

		sw		a0,O_ARG0(fp)
		sw		a1,O_ARG1(fp)
		sw		a2,O_ARG2(fp)

		li		v0,SYS_write

		lw		a0,O_ARG0(fp)
		lw		a1,O_ARG1(fp)
		lw		a2,O_ARG2(fp)

		syscall

		bne	a3,zero,write_error

		b		write_unwind

write_error:
		li		v0,-1

write_unwind:
		lw		gp,O_GP(sp)
		lw		fp,O_FP(sp)
		lw		ra,O_RA(sp) 
		addiu		sp, sp, SSIZE
		jr		ra
		.end		my_write
\end{Verbatim}
\end{scriptsize}
		\subsection{Código mymalloc.S}


\begin{scriptsize}
\begin{Verbatim}
#include <sys/syscall.h>
#include <mips/regdef.h>

#define MYMALLOC_SIGNATURE 0xdeadbeef

#ifndef PROT_READ
#define PROT_READ 0x01
#endif

#ifndef PROT_WRITE
#define PROT_WRITE 0x02
#endif

#ifndef MAP_PRIVATE
#define MAP_PRIVATE 0x02
#endif

#ifndef MAP_ANON
#define MAP_ANON 0x1000
#endif

#define MALLOC_SS			56

#define MALLOC_O_ARG 		(MALLOC_SS)

#define MALLOC_O_RA  		48
#define MALLOC_O_FP			44
#define MALLOC_O_GP			40

#define MALLOC_LTA_SIZE		36	
#define MALLOC_LTA_RVAL		32 

#define MALLOC_ABA_7		28
#define MALLOC_ABA_6		24

#define MALLOC_ABA_5		16



	.text
	.align	2
	.globl	mymalloc
	.ent	mymalloc
mymalloc:
	subu	sp, sp, MALLOC_SS 
	sw	ra, MALLOC_O_RA(sp)
	sw	$fp,MALLOC_O_FP(sp)
	sw	gp, MALLOC_O_GP(sp)

	sw	a0, MALLOC_O_ARG(sp)  # Temporary: original allocation size.

	sw	a0, MALLOC_LTA_SIZE(sp)  # Temporary: actual allocation size.
	li	t0, -1
	sw	t0, MALLOC_LTA_RVAL(sp)  # Temporary: return value (defaults to -1).

	move	$fp, sp

	# Adjust the original allocation size to a 4-byte boundary.
	#
	lw	t0, MALLOC_O_ARG(sp)
	addiu	t0, t0, 3
	and	t0, t0, 0xfffffffc
	sw	t0, MALLOC_O_ARG(sp)

	# Increment the allocation size by 12 units, in order to 
	# make room for the allocation signature, block size and
	# trailer information.
	#
	lw	t0, MALLOC_O_ARG(sp)
	addiu	t0, t0, 12
	sw	t0, MALLOC_LTA_SIZE(sp)

	# mmap(0, sz, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANON, -1, 0)
	#
	li	v0, SYS_mmap
	li	a0, 0
	lw	a1, MALLOC_LTA_SIZE(sp)
	li	a2, PROT_READ|PROT_WRITE
	li	a3, MAP_PRIVATE|MAP_ANON

	# According to mmap(2), the file descriptor 
	# must be specified as -1 when using MAP_ANON.
	#
	li	t0, -1
	sw	t0,MALLOC_ABA_5(sp)

	# Use a trivial offset.
	#
	li	t0, 0
	sw	t0,MALLOC_ABA_6(sp)
	sw	t0,MALLOC_ABA_7(sp)


	# Excecute the syscall, save the return value.
	#
	syscall
	sw	v0, MALLOC_LTA_RVAL(sp)
	beqz	v0, mymalloc_return

	# Success. Check out the allocated pointer.
	#
	lw	t0, MALLOC_LTA_RVAL(sp)
	li	t1, MYMALLOC_SIGNATURE
	sw	t1, 0(t0)

	# The actual allocation size goes right after the signature.
	#
	lw	t0, MALLOC_LTA_RVAL(sp)
	lw	t1, MALLOC_LTA_SIZE(sp)
	sw	t1,  4(t0)

	# Trailer information.
	#
	lw	t0, MALLOC_LTA_SIZE(sp) # t0: actual allocation size.
	lw	t1, MALLOC_LTA_RVAL(sp) # t1: Pointer.
	addu	t1, t1, t0 # t1 now points to the trailing 4-byte area.
	xor	t2, t0, MYMALLOC_SIGNATURE
	sw	t2, -4(t1)

	# Increment the result pointer.
	#
	lw	t0, MALLOC_LTA_RVAL(sp)
	addiu	t0, t0, 8
	sw	t0, MALLOC_LTA_RVAL(sp)

mymalloc_return:
	# Restore the return value.
	#
	lw	v0, MALLOC_LTA_RVAL(sp)

	# Destroy the stack frame.
	#
	move	sp, $fp
	lw	ra, MALLOC_O_RA(sp)
	lw	$fp, MALLOC_O_FP(sp)
	addu	sp, sp,MALLOC_SS

	j	ra
	.end	mymalloc


#define FREE_SS				40

#define FREE_O_ARG 			(FREE_SS)

#define FREE_O_RA  			32
#define FREE_O_FP			28
#define FREE_O_GP			24

#define FREE_LTA_ARG		20	 
#define FREE_LTA_ACTUAL		16	 

	.globl	myfree
	.ent	myfree
myfree:
	subu	sp, sp, FREE_SS		

	sw		ra, FREE_O_RA(sp)			
	sw		$fp,FREE_O_FP(sp)
	sw		gp,FREE_O_GP(sp)						


	sw	a0, FREE_O_ARG(sp)  # Temporary: argument pointer.			
	sw	a0, FREE_LTA_ACTUAL(sp)  # Temporary: actual mmap(2) pointer.	
	move	$fp, sp

	# Calculate the actual mmap(2) pointer.
	#
	lw	t0, FREE_O_ARG(sp)			
	subu	t0, t0, 8
	sw	t0, FREE_LTA_ACTUAL(sp)		

	# XXX Sanity check: the argument pointer must be checked
	# in before we try to release the memory block.
	#
	# First, check the allocation signature.
	#
	lw	t0, FREE_LTA_ACTUAL(sp) # t0: actual mmap(2) pointer.
	lw	t1, 0(t0)
	bne	t1, MYMALLOC_SIGNATURE, myfree_die

	# Second, check the memory block trailer.
	#
	lw	t0, FREE_LTA_ACTUAL(sp) # t0: actual mmap(2) pointer. 	
	lw	t1, 4(t0)  # t1: actual mmap(2) block size.
	addu	t2, t0, t1 # t2: trailer pointer.
	lw	t3, -4(t2)
	xor	t3, t3, t1
	bne	t3, MYMALLOC_SIGNATURE, myfree_die

	# All checks passed. Try to free this memory area.
	#
	li	v0, SYS_munmap
	lw	a0, FREE_LTA_ACTUAL(sp) # a0: actual mmap(2) pointer.	
	lw	a1, 4(a0)  # a1: actual allocation size.
	syscall

	# Bail out if we cannot unmap this memory block.
	#
	bnez	v0, myfree_die

	# Success.
	#
	j myfree_return

myfree_die:
	# Generate a segmentation faul by writing to the first
	# byte of the adress space (a.ka. the NULL pointer).
	#
	sw t0, 0(zero)

myfree_return:
	# Destroy the stack frame.
	#
	move	sp, $fp
	lw	ra,  FREE_O_RA(sp)		
	lw	$fp, FREE_O_FP(sp)	
	addu	sp, sp,FREE_SS

	jr	ra
.end	myfree


# void *mymemcpy(void *dest, void *src, size_t n)
# 
#define MEMCPY_SS	8
#define MEMCPY_O_ARG	(MEMCPY_SS)
#define MEMCPY_O_FP	4
#define MEMCPY_O_GP	0

.globl	mymemcpy
.ent 	mymemcpy
mymemcpy:
	.frame $fp, MEMCPY_SS, ra
	.set  noreorder
   	.cpload  t9
   	.set  reorder

	subu	sp, sp, MEMCPY_SS
	sw	$fp, MEMCPY_O_FP(sp)
	sw	gp, MEMCPY_O_GP(sp)
	move	$fp, sp
	sw	a0, MEMCPY_O_ARG(sp)	# guardo dest en el stack frame del caller
	sw	a1, MEMCPY_O_ARG+4(sp)	# guardo src en el stack frame del caller
	sw	a2, MEMCPY_O_ARG+8(sp)	# guardo n en el stack frame del caller

	li	t0, 0			# cargo en t0 el valor cero.
	beqz 	a2, mymemcpy_return	# si n es cero termina la funcion.
	
iterar:
	addu	t1, t0, a1	# t1 = src + desplaz.
	addu	t2, t0, a0	# t2 = dest + desplaz.
	lb	t3, 0(t1)	# t3 = byte leido de t1.
	sb	t3, 0(t2)	# t3 = byte a escribir en t2.
	addiu	t0, t0, 1	# incremento t0.
	bne	t0, a2, iterar	# si t0 no es igual al n pasado como parametro sigo iterando.

	subu	t2, t2, t0
	addiu	t2, t2, 1
	move	v0, t2		# guardo como retorno en v0 la direccion del buffer dest.

mymemcpy_return:
	move	sp, $fp
	lw	$fp, MEMCPY_O_FP(sp)
	addiu	sp, sp, MEMCPY_SS
	jr	ra

.end mymemcpy

# myrealloc(void *, size_t) 
#define REALLOC_SS			48

#define REALLOC_O_ARG 			(REALLOC_SS)

#define REALLOC_O_RA  			40
#define REALLOC_O_FP			36
#define REALLOC_O_GP			32

#define REALLOC_LTA_NEW_DATA_PTR	28
#define REALLOC_LTA_OLD_BLOCK_SIZE	24	 
#define REALLOC_LTA_ACTUAL_MMAP_PTR	20
#define REALLOC_LTA_NEW_BLOCK_SIZE	16
.globl	myrealloc
.ent 	myrealloc
myrealloc:
	.frame $fp, REALLOC_SS, ra
	.set  noreorder
   	.cpload  t9
   	.set  reorder

	subu	sp, sp, REALLOC_SS
	sw	ra, REALLOC_O_RA(sp)			
	sw	$fp, REALLOC_O_FP(sp)
	sw	gp, REALLOC_O_GP(sp)

	sw	a0, REALLOC_O_ARG(sp)  	# Guardo el primer argumento en stack frame del caller
	sw	a1, REALLOC_O_ARG+4(sp)	# Guardo segundo argumento en stack frame del caller		
	sw	a0, REALLOC_LTA_ACTUAL_MMAP_PTR(sp)  # Temporary: actual mmap(2) pointer.
	sw	a1, REALLOC_LTA_NEW_BLOCK_SIZE(sp) # Temporary: new block size	
	move	$fp, sp

	# Calculate the actual mmap(2) pointer.
	#
	lw	t0, REALLOC_O_ARG(sp)			
	subu	t0, t0, 8
	sw	t0, REALLOC_LTA_ACTUAL_MMAP_PTR(sp)		

	# XXX Sanity check: the argument pointer must be checked
	# in before we try to release the memory block.
	#
	# First, check the allocation signature.
	#
	lw	t0, REALLOC_LTA_ACTUAL_MMAP_PTR(sp) # t0: actual mmap(2) pointer.
	lw	t1, 0(t0)
	bne	t1, MYMALLOC_SIGNATURE, myrealloc_die

	# Second, check the memory block trailer.
	#
	lw	t0, REALLOC_LTA_ACTUAL_MMAP_PTR(sp) # t0: actual mmap(2) pointer. 	
	lw	t1, 4(t0)  # t1: actual mmap(2) block size.
	sw	t1, REALLOC_LTA_OLD_BLOCK_SIZE(sp)
	addu	t2, t0, t1 # t2: trailer pointer.
	lw	t3, -4(t2)
	xor	t3, t3, t1
	bne	t3, MYMALLOC_SIGNATURE, myrealloc_die

	lw	a0, REALLOC_LTA_NEW_BLOCK_SIZE(sp)	# cargo el argumento para el malloc
	la	t9, mymalloc
	jalr	t9					# llamo al malloc
	sw	v0, REALLOC_LTA_NEW_DATA_PTR(sp) 	#guardo el puntero del malloc
	beqz	v0, myrealloc_return			#si no se puede asignar salgo

	lw	t0, REALLOC_LTA_NEW_BLOCK_SIZE(sp)
	lw	t1, REALLOC_LTA_OLD_BLOCK_SIZE(sp)
	lw	a2, REALLOC_LTA_NEW_BLOCK_SIZE(sp)
	bgeu	t0, t1, seguir
	lw	a2, REALLOC_LTA_OLD_BLOCK_SIZE(sp)
seguir:	lw	a0, REALLOC_LTA_NEW_DATA_PTR(sp)
	lw	a1, REALLOC_O_ARG(sp)
	la	t9, mymemcpy
	jalr	t9

	lw	a0, REALLOC_O_ARG(sp)
	la	t9, myfree
	jalr	t9
	
	j	myrealloc_return

myrealloc_die:
	# Generate a segmentation faul by writing to the first
	# byte of the adress space (a.ka. the NULL pointer).
	#
	sw t0, 0(zero)

myrealloc_return:
	# Valor de retorno
	lw 	v0, REALLOC_LTA_NEW_DATA_PTR(sp)

	# Destruyo el stack frame
	#
	move sp, $fp
	lw	ra,  REALLOC_O_RA(sp)		
	lw	$fp, REALLOC_O_FP(sp)	
	addu	sp, sp, REALLOC_SS
	j	ra
.end	myrealloc
\end{Verbatim}
\end{scriptsize}

		\subsection{Código mergesort.S}


\begin{scriptsize}
\begin{Verbatim}
# mergesort.S 							
# 								
# - Argumentos:							
# 	* a0: dirección inicial del arreglo a ordenar.		
#	* a1: tamaño del arreglo.				
#								
# - No devuelve ningún valor de retorno. 			
#								
# - Stack frame: 56 bytes					
#	* Los 32 superiores se usan para el SRA + padding.	
#	* Los 24 inferiores son espacio reservado para 	
#	  el ABA (5 argumentos + padding).										


#include <mips/regdef.h>
#include <sys/syscall.h>

#define 	SSIZE 	(56)

#define		O_RA 	(48)
#define		O_FP 	(44)
#define		O_GP	(40)

#define 	O_S3 	(36)
#define 	O_S2 	(32)
#define 	O_S1 	(28)
#define 	O_S0 	(24)

#define 	O_ARG0	(SSIZE)
#define 	O_ARG1	((SSIZE) + 4)


#void mergeSort(char* entrada, int tamanioEntrada)

	.text
	.align 	2
	.globl	merge_sort
	.ent	merge_sort

merge_sort:
   	.frame $fp, SSIZE, ra
   	.set noreorder
   	.cpload t9
   	.set reorder     
	
		subu	sp,sp,SSIZE 		#crea el stack.

		sw 	s0, O_S0(sp)
		sw 	s1, O_S1(sp)
		sw 	s2, O_S2(sp)
		sw 	s3, O_S3(sp)

		#sw	gp, O_GP(sp)
		.cprestore O_GP
		sw	$fp, O_FP(sp)
		sw	ra, O_RA(sp) 	

		move	$fp, sp

		sw	a0, O_ARG0($fp)
		sw	a1, O_ARG1($fp)


		lw 	t0, O_ARG1($fp) 	#t0 es tamanioEntrada
		addi 	t1, t0, -1
		
		beq 	t1, zero, SALIDA 	#if (tamanioEntrada > 1) sigue, si no, destruye el stack y sale.

		srl 	s0, t0, 1 		#s0 es tamanioBuffer1 = tamanioEntrada/2
		subu 	s1, t0, s0		#s1 es tamanioBuffer2 = tamanioEntrada - tamanioBuffer1

						
		la 	t9, mymalloc 		#llama a mymalloc para buffer1 y buffer2.
		move	a0, s0
		jalr	t9
		move 	s2, v0			#s2 es la dirección inicial de buffer1.
		
		beqz 	v0, BAD_ALLOC
		
		la 	t9, mymalloc
		move 	a0, s1
		jalr 	t9
		move 	s3, v0 			#s3 es la dirección inicial de buffer2.

		beqz 	v0, BAD_ALLOC
						#fin de los malloc.
		
						#llamadas a memcpy para llenar los buffers con el contenido del array.
		move 	a0, s2
		lw 	a1, O_ARG0($fp) 	#carga la dirección inicial del array (a0) en a1.
		move 	a2, s0		
		la 	t9, mymemcpy
		jalr 	t9

		move 	a0, s3
		lw 	a1, O_ARG0($fp)
		addu 	a1, a1, s0 		#dirección donde comienza la 2da mitad del array.
		move 	a2, s1
		la 	t9, mymemcpy
		jalr 	t9
						#fin de los memcpy.

		move 	a0, s2 			#llamadas recursivas a merge_sort para buffer1 y buffer2
		move 	a1, s0
		la 	t9, merge_sort
		jalr 	t9
		
		move 	a0, s3
		move 	a1, s1
		la 	t9, merge_sort
		jalr 	t9
						#fin de los merge sort.

		move 	a0, s2 			#llamada a merge_buffers
		move 	a1, s0
		move 	a2, s3
		move 	a3, s1
		lw 	t8, O_ARG0($fp)
		sw 	t8, 16($fp) 		#el 5to argumento lo pasa por stack
		la 	t9, merge_buffers
		jalr 	t9

		move 	a0, s2			#llama a myfree para buffer1 y buffer2
		la 	t9, myfree
		jalr 	t9

		move 	a0, s3
		la 	t9, myfree
		jalr 	t9 			#fin de los free.

		li 	v0, 1
	
UNWIND: 	lw 	s0, O_S0($fp)		#destruye el stack
		lw 	s1, O_S1($fp)
		lw 	s2, O_S2($fp)
		lw 	s3, O_S3($fp)

		move 	sp, $fp
		lw	gp, O_GP($fp)
		lw 	ra, O_RA($fp)
		lw	$fp, O_FP($fp)
		
		addiu 	sp, sp, SSIZE
		jr 	ra

SALIDA:		li 	v0, 1
		b 	UNWIND
		
BAD_ALLOC: 	li 	v0, 0 			#el 0 indica que el algoritmo no pudo finalizar correctamente
		b 	UNWIND

	.end 	merge_sort
\end{Verbatim}
\end{scriptsize}

		\subsection{Código mergebuffers.S}


\begin{scriptsize}
\begin{Verbatim}
# mergebuffers.S 							
# 								
# - Argumentos:							
# 	* a0: dirección inicial de buffer1.		
#	* a1: tamaño de buffer1.
# 	* a2: dirección inicial de buffer2.		
#	* a3: tamaño de buffer2.
#	* stack: dirección inicial de memoria para guardar el buffer resultante.
#								
# - No devuelve ningún valor de retorno. 			
#								
# - Stack frame: 16 bytes para el SRA + padding. Por ser función hoja, no reserva espacio para ABA.
										

#include <mips/regdef.h>
#include <sys/syscall.h>

#define 	SSIZE 	(16)

#define		O_FP 	(8)
#define		O_GP	(4)
#define 	O_S4 	(0)

#define 	O_ARG0	(SSIZE)
#define 	O_ARG1	((SSIZE) + 4)
#define 	O_ARG2	((SSIZE) + 8)
#define 	O_ARG3	((SSIZE) + 12)
#define 	O_ARG4	((SSIZE) + 16)


#void mergeBuffers (char* buffer1, int tamanioBuffer1, char* buffer2, int tamanioBuffer2, char* salida)

	.text
	.align 	2
	.globl	merge_buffers
	.ent	merge_buffers

merge_buffers:
   	.frame $fp, SSIZE, ra
   	.set noreorder
   	.cpload t9
   	.set reorder     
	
		subu	sp,sp,SSIZE 		#crea el stack.

		sw 	s4, O_S4(sp)

		#sw	gp, O_GP(sp)
		.cprestore O_GP
		sw	$fp, O_FP(sp) 
		
		move	$fp, sp

		sw	a0, O_ARG0($fp)
		sw	a1, O_ARG1($fp)
		sw	a2, O_ARG2($fp)
		sw	a3, O_ARG3($fp)
		lw 	s4, O_ARG4($fp) 	#recupera el 5to argumento del stack en s4

		move 	t1, zero 		#pBuffer1 = 0
		move 	t2, zero 		#pBuffer2 = 0
		move 	t0, zero 		#pSalida = 0 (son los índices para recorrer los buffers)

BUCLE_PPAL:	beq 	t1, a1, BUCLE_BUFF1 	#chequea las dos condiciones del bucle principal
		beq 	t2, a3, BUCLE_BUFF1
		
		addu 	t6, t1, a0
		addu 	t7, t2, a2		

		lb 	t3, 0(t6) 		#t3 es buffer1[pBuffer1]
		lb 	t4, 0(t7) 		#t4 es buffer2[pBuffer2]
		sub 	t5, t4, t3
		blez 	t5, ELSE

		addu 	t8, t0, s4
		sb 	t3, 0(t8)
		addiu 	t1, t1, 1
		b 	FIN_DEL_CICLO

ELSE:		addu 	t8, t0, s4
		sb 	t4, 0(t8)
		addiu 	t2, t2, 1

FIN_DEL_CICLO: 	addiu 	t0, t0, 1
		b 	BUCLE_PPAL


BUCLE_BUFF1: 	beq 	t1, a1, BUCLE_BUFF2

		addu 	t6, t1, a0
		addu 	t8, t0, s4

		lb 	t3, 0(t6)
		sb 	t3, 0(t8)

		addiu 	t1, t1, 1
		addiu 	t0, t0, 1

		b 	BUCLE_BUFF1

BUCLE_BUFF2: 	beq 	t2, a3, SALIDA

		addu 	t7, t2, a2
		addu 	t8, t0, s4

		lb 	t4, 0(t7)
		sb 	t4, 0(t8)

		addiu 	t2, t2, 1
		addiu 	t0, t0, 1

		b 	BUCLE_BUFF2

SALIDA:		move 	sp, $fp

		lw 	s4, O_S4($fp)
		lw	gp, O_GP($fp)
		lw	$fp, O_FP($fp)
		
		addiu 	sp, sp, SSIZE
		jr 	ra

	.end 	merge_buffers
\end{Verbatim}
\end{scriptsize}

\section{Pruebas}
\subsection{Archivos de Prueba}
\subsubsection{digits.txt}
\begin{scriptsize}
\begin{Verbatim}
# hexdump -C digits.txt
00000000  39 38 37 36 35 34 33 32  31 30                    |9876543210|
0000000a
\end{Verbatim}
\end{scriptsize}
\subsubsection{letters.txt}
\begin{scriptsize}
\begin{Verbatim}
# hexdump -C letters.txt
00000000  61 41 62 42 63 43 64 44  65 45 66 46 67 47 68 48  |aAbBcCdDeEfFgGhH|
00000010  69 49 6a 4a 6b 4b 6c 4c  6d 4d 6e 4e 6f 4f 70 50  |iIjJkKlLmMnNoOpP|
00000020  71 51 72 52 73 53 74 54  75 55 76 56 77 57 78 58  |qQrRsStTuUvVwWxX|
00000030  79 59 7a 5a                                       |yYzZ|
00000034
\end{Verbatim}
\end{scriptsize}
\subsubsection{random.txt}
\begin{scriptsize}
\begin{Verbatim}
# head -c 64 /dev/urandom > random.txt
# hexdump -C random.txt
00000000  a2 34 8e 49 21 38 35 14  75 c4 dc 9f 5b a3 69 0f  |.4.I!85.u...[.i.|
00000010  8a 79 66 c0 ac d2 76 8a  cc 05 5e 4d 9e d3 4a a4  |.yf...v...^M..J.|
00000020  16 1f 0d 62 cd 63 6c 0e  e0 b5 ef 2a b9 de 50 a5  |...b.cl....*..P.|
00000030  84 3a fe 32 \da ce 61 1e  b9 f3 aa b1 4e a2 2e 50  |.:.2..a.....N..P|
00000040
\end{Verbatim}
\end{scriptsize}
\subsubsection{vacio.txt}
\begin{scriptsize}
\begin{Verbatim}
# > vacio.txt
# hexdump -C vacio.txt
\end{Verbatim}
\end{scriptsize}
\subsection{Corridas de Prueba}
\subsubsection{digits.txt}
\begin{scriptsize}
\begin{Verbatim}
# ./tp1 <digits.txt
0123456789
\end{Verbatim}
\end{scriptsize}
\subsubsection{letters.txt}
\begin{scriptsize}
\begin{Verbatim}
# ./tp1 <letters.txt
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz
\end{Verbatim}
\end{scriptsize}
\subsubsection{random.txt}
\begin{scriptsize}
\begin{Verbatim}
# ./tp1 < random.txt > sorted.txt
# hexdump -C sorted.txt
00000000  84 8a 8a 8e 9e 9f a2 a2  a3 a4 a5 aa ac b1 b5 b9  |................|
00000010  b9 c0 c4 cc cd ce d2 d3  da dc de e0 ef f3 fe 05  |................|
00000020  0d 0e 0f 14 16 1e 1f 21  2a 2e 32 34 35 38 3a 49  |.......!*.2458:I|
00000030  4a 4d 4e 50 50 5b 5e 61  62 63 66 69 6c 75 76 79  |JMNPP[^abcfiluvy|
00000040
\end{Verbatim}
\end{scriptsize}
\subsubsection{vacio.txt}
\begin{scriptsize}
\begin{Verbatim}
# ./tp1 < vacio.txt > salidavacio.txt
# diff vacio.txt salidavacio.txt
#
\end{Verbatim}
\end{scriptsize}

\section{Conclusiones}

Con el desarrollo de este Trabajo Práctico hemos podido simular el comportamiento del compilador a la hora de generar el código fuente en lenguaje ensamblador (.S). Tal conclusión se ha alcanzado a partir de verificar los resultados obtenidos habiendo realizado todos los procedimientos en un solo lenguaje (C) y observando que los mismos coinciden. 
\newline
A su vez hemos podido interiorizarnos en el concepto de ABI, aplicando dicha interface a la presente entrega. Para ello, hemos investigado el conjunto de instrucciones que nos provee MIPS y las hemos aplicado, respetando las Function Calling Conventions[2]. Además hemos ahondando en el tema de las directivas del \emph{assembly} para entender mejor su funcionamiento.


Para finalizar, hemos concluido que existen ventajas y desventajas a la hora de programar en assembly respecto de un lenguaje de alto nivel.

La primer ventaja a destacar es la velocidad del programa. Muchas veces el código generado por un compilador es menos eficiente que el equivalente que un programador escribiría. La razón es que el compilador no posee la inteligencia de un ser humano y podría desperdiciar tiempo realizando procesos que no son necesarios. Este aspecto no es absoluto dado que tambíen depende de la habilidad del programador. Además, frente al problema resuelto en este trabajo no se percibe esta diferencia.

Otro aspecto a destacar es el tama\~no del código generado. Por la misma razón que se menciono anteriormente, un compilador genera más código de maquina que el necesario y el tama\~no del programa ejecutable crece.

Por otro lado, al ser un lenguaje más primitivo, se tienen ciertas desventajas respecto a los lenguajes de alto nivel. 

Una de ellas es el tiempo de programación, dado que se requieren más instrucciones para realizar el mismo proceso en comparación con un lenguaje de alto nivel. 

Muchas veces el código assembly es menos entendible. En nuestro caso, el codigo C desarrollado es mucho más comprensible que el assembly equivalente.

Otra desventaja que hemos experemintado es que los código fuente son mucho más grandes, razón por la cual aumenta el tiempo de desarrollo. En nuestro caso particular esta desventaja se ha hecho visible al exponer los códigos en C correspondientes a los módulos desarrollados en assembly. 

Por último, la falta de portabilidad es otra desventaja, dado que existe un lenguaje ensamblador para cada máquina. En cambio, programando en un lenguaje de alto nivel esta desventaja es mucho menos notoria ya que al recompilar el código (realizado para una máquina) adecuadamente la mayoría del mismo  será reutilizable en otra.


Finalmente podemos agregar que, dado que la programación en lenguaje ensamblador depende de la arquitectura del computador sobre el cual se trabaja, es importante para entender el funcionamiento interno de la máquina comprendiendo cómo es su estructura básica.
\newpage
\section{Apéndice A}
\subsection{Diagrama de secuencia}

En este apéndice se expone un diagrama de secuencia que permite ver el orden en que se ejecuta cada método. \\
\newline
\put(-125, 0){\includegraphics[width=19cm, height=18cm]{secuenciatp1.png}}

\section{Apéndice B}
\subsection{Pruebas unitarias}
\begin{itemize}
      
	
	\item \textbf{Entrada vacía: }
    	Si ejecutamos la siguiente secuencia de comandos en el shell:\\
    	\$echo -n ``'' $>$ entrada.txt \\
   	\$cat entrada.txt $|$ ./tp1\\
      	En este caso, cuando se ingresen datos de un archivo vacío, la ejecución termina sin error. \\
  	    
      	\item \textbf{Entrada con orden invertido: }
      	Si ejecutamos la siguiente secuencia de comandos:\\
      	\$echo -n ``9876543210'' $|$ ./tp1\\
      	0123456789\$ \\
      	Como se puede observar, los números se ordenaron correctamente. \\

      	\item \textbf{Entrada con números repetidos: }
	Si la entrada presenta caracteres repetidos, el orden en el resultado 
	es correcto. \\
	\$echo -n ``0112781121401'' $|$ ./tp1\\
	0011111122478\$ \\

	\item \textbf{No se ingresa entrada: }
	El caso de que no se ingrese una entrada por stdin, la ejecución del programa se detiene hasta que el usuario la ingrese.
	\$./tp1\\
	\$68945\\
	45689\$
	
	\item \textbf{Archivo de 1000 caracteres}\\
\begin{scriptsize}
\begin{Verbatim}
# head -c 1000 /dev/urandom >random1.txt
# ./tp1 < random1.txt >sorted1.txt
# hexdump -C sorted1.txt
00000000  80 80 80 81 81 81 81 81  82 82 82 82 82 82 83 83  |................|
00000010  83 83 83 83 83 84 85 85  85 85 86 86 86 86 87 87  |................|
00000020  87 87 87 87 87 88 88 88  88 89 89 8a 8a 8b 8b 8b  |................|
00000030  8b 8c 8c 8d 8d 8d 8d 8d  8e 8e 90 90 90 90 91 91  |................|
00000040  92 93 93 93 93 93 94 94  94 94 94 94 94 95 95 95  |................|
00000050  95 96 96 96 97 97 98 98  98 99 99 99 99 99 9a 9a  |................|
00000060  9a 9a 9a 9a 9b 9b 9b 9c  9c 9d 9d 9e 9e 9e 9e 9e  |................|
00000070  9f 9f 9f a0 a0 a0 a0 a0  a1 a1 a1 a2 a2 a2 a2 a3  |................|
00000080  a4 a4 a4 a4 a4 a4 a4 a5  a5 a5 a5 a5 a5 a5 a6 a6  |................|
00000090  a6 a6 a7 a8 a8 a8 a8 a8  a8 a9 a9 a9 a9 aa aa aa  |................|
000000a0  aa ab ab ab ab ab ab ab  ab ab ab ac ac ac ac ad  |................|
000000b0  ad ad ad ae ae ae ae ae  ae ae ae af af b0 b0 b0  |................|
000000c0  b1 b1 b1 b1 b1 b1 b1 b1  b1 b1 b1 b2 b2 b2 b3 b3  |................|
000000d0  b3 b4 b4 b4 b4 b5 b5 b6  b6 b6 b6 b7 b7 b7 b7 b8  |................|
000000e0  b8 b8 b9 b9 b9 ba ba ba  ba bb bb bb bb bb bb bb  |................|
000000f0  bc bc bc bc bc bc bc bc  bc bd bd bd bd be be be  |................|
00000100  be be be be bf bf c0 c0  c1 c1 c1 c2 c2 c2 c3 c3  |................|
00000110  c3 c3 c4 c4 c4 c4 c4 c4  c5 c6 c6 c6 c6 c7 c7 c7  |................|
00000120  c7 c7 c8 c9 c9 c9 c9 c9  c9 c9 ca ca ca ca cb cb  |................|
00000130  cb cb cb cc cc cc cc cc  cc cc cc cc cc cd cd cd  |................|
00000140  ce ce cf cf cf cf cf cf  cf d0 d0 d0 d0 d1 d1 d1  |................|
00000150  d1 d2 d2 d2 d3 d3 d3 d3  d3 d3 d3 d4 d4 d4 d4 d4  |................|
00000160  d4 d5 d5 d5 d5 d5 d5 d6  d6 d6 d6 d7 d7 d7 d7 d7  |................|
00000170  d7 d8 d8 d8 d8 d9 d9 d9  da da da db db db db dc  |................|
00000180  dc dc dc dd de de de de  df df df e0 e0 e0 e0 e0  |................|
00000190  e0 e0 e1 e1 e1 e1 e2 e2  e2 e3 e3 e3 e4 e4 e5 e5  |................|
000001a0  e5 e5 e5 e5 e5 e6 e6 e6  e6 e6 e6 e7 e7 e8 e9 e9  |................|
000001b0  e9 e9 e9 ea ea ea ea ea  ea ea eb ec ec ed ed ed  |................|
000001c0  ed ed ee ee ee ee ee ef  ef ef f0 f0 f0 f1 f1 f1  |................|
000001d0  f1 f1 f1 f1 f2 f2 f2 f3  f3 f3 f3 f3 f3 f3 f3 f4  |................|
000001e0  f5 f5 f5 f6 f6 f7 f7 f7  f7 f8 f8 f8 f8 f8 f8 f9  |................|
000001f0  f9 fa fa fb fb fb fb fb  fc fd fe fe fe fe fe fe  |................|
00000200  ff ff ff 00 00 00 00 00  00 01 01 01 01 01 01 02  |................|
00000210  02 03 03 03 03 04 04 04  04 04 04 05 05 05 05 06  |................|
00000220  06 06 06 06 07 07 07 07  08 08 08 08 08 08 08 09  |................|
00000230  09 09 09 09 09 0a 0a 0a  0a 0b 0b 0c 0c 0c 0d 0d  |................|
00000240  0d 0d 10 10 11 11 11 11  12 12 12 12 13 13 14 14  |................|
00000250  14 14 15 15 15 16 16 16  16 17 17 18 18 18 18 19  |................|
00000260  19 19 19 1a 1a 1b 1b 1b  1b 1c 1c 1c 1c 1c 1c 1d  |................|
00000270  1d 1e 1e 1e 1f 1f 1f 1f  20 20 20 21 21 21 21 21  |........   !!!!!|
00000280  21 22 22 22 23 23 24 24  24 24 25 25 25 25 25 26  |!"""##$$$$%%%%%&|
00000290  27 27 27 27 28 28 28 28  28 28 29 29 29 29 29 2a  |''''(((((()))))*|
000002a0  2a 2a 2a 2a 2a 2a 2a 2b  2b 2b 2b 2b 2b 2b 2c 2c  |*******+++++++,,|
000002b0  2d 2d 2d 2d 2d 2d 2d 2e  2e 2f 30 30 30 30 31 31  |-------../000011|
000002c0  31 31 31 32 32 32 32 32  33 33 34 34 34 35 35 35  |1112222233444555|
000002d0  35 35 35 35 35 36 36 37  37 37 37 37 38 38 38 38  |5555566777778888|
000002e0  38 39 39 39 3b 3b 3b 3b  3b 3c 3c 3c 3c 3c 3c 3c  |8999;;;;;<<<<<<<|
000002f0  3d 3d 3d 3d 3d 3d 3d 3d  3d 3d 3e 3f 3f 3f 40 40  |==========>???@@|
00000300  40 41 41 41 41 42 42 43  43 43 43 43 44 44 44 44  |@AAAABBCCCCCDDDD|
00000310  44 44 45 45 45 45 45 46  46 46 46 46 46 47 47 48  |DDEEEEEFFFFFFGGH|
00000320  48 48 48 49 49 49 49 49  4a 4a 4a 4a 4a 4a 4a 4b  |HHHIIIIIJJJJJJJK|
00000330  4c 4c 4c 4c 4d 4d 4d 4d  4d 4d 4e 4e 4e 4f 4f 4f  |LLLLMMMMMMNNNOOO|
00000340  50 50 51 51 51 51 51 52  52 52 52 54 55 55 55 56  |PPQQQQQRRRRTUUUV|
00000350  56 57 57 57 57 57 58 58  58 58 58 58 58 58 59 59  |VWWWWWXXXXXXXXYY|
00000360  59 59 5a 5a 5a 5b 5b 5b  5c 5c 5c 5c 5d 5d 5d 5d  |YYZZZ[[[\\\\]]]]|
00000370  5d 5e 5e 5e 5e 5f 5f 5f  5f 5f 60 60 60 60 60 60  |]^^^^_____``````|
00000380  61 61 62 62 62 62 62 62  62 62 63 63 63 64 64 65  |aabbbbbbbbcccdde|
00000390  65 65 65 66 66 66 66 66  67 67 68 68 68 68 69 69  |eeefffffgghhhhii|
000003a0  6a 6a 6a 6a 6a 6a 6b 6b  6b 6c 6c 6c 6d 6d 6d 6e  |jjjjjjkkklllmmmn|
000003b0  6e 6f 6f 6f 6f 70 70 71  71 71 71 71 73 73 74 74  |nooooppqqqqqsstt|
000003c0  75 75 75 75 75 76 76 76  76 76 76 77 77 77 77 77  |uuuuuvvvvvvwwwww|
000003d0  78 78 78 78 78 78 78 78  79 79 79 7a 7b 7b 7c 7c  |xxxxxxxxyyyz{{|||
000003e0  7c 7d 7d 7e 7e 7e 7f 7f                           ||}}~~~..|
000003e8
\end{Verbatim}
\end{scriptsize}	
La ejecución se realizó con exito y los bytes fueron ordenados.\\

\item \textbf{Archivo de 1 MB}\\
\begin{scriptsize}
\begin{Verbatim}
# head -c 1048576 /dev/urandom > random2.txt
# ./tp1 < random2.txt > salida1M.txt
#
\end{Verbatim}
\end{scriptsize}

La ejecución se realizó con éxito y los bytes fueron ordenados.\\
    

      \end{itemize}

	\section{Apéndice C}
	\subsection{Bug Fixing}
Se corrigió un bug en la función myrealloc. Se intercambiaron las siguientes lineas:\\
\begin{scriptsize}
\begin{Verbatim}
	lw	a2, REALLOC_LTA_NEW_BLOCK_SIZE(sp)
	bgeu	t0, t1, seguir
	lw	a2, REALLOC_LTA_OLD_BLOCK_SIZE(sp)
seguir:	lw	a0, REALLOC_LTA_NEW_DATA_PTR(sp)
\end{Verbatim}
\end{scriptsize}
por las siguientes:\\
\begin{scriptsize}
\begin{Verbatim}
	lw	a2, REALLOC_LTA_OLD_BLOCK_SIZE(sp)
	bgeu	t0, t1, seguir
	lw	a2, REALLOC_LTA_NEW_BLOCK_SIZE(sp)
seguir:	lw	a0, REALLOC_LTA_NEW_DATA_PTR(sp)
\end{Verbatim}
\end{scriptsize}


El código de esta función quedó de la siguiente manera:\\
\begin{scriptsize}
\begin{Verbatim}
# myrealloc(void *, size_t) 
#define REALLOC_SS			48

#define REALLOC_O_ARG 			(REALLOC_SS)

#define REALLOC_O_RA  			40
#define REALLOC_O_FP			36
#define REALLOC_O_GP			32

#define REALLOC_LTA_NEW_DATA_PTR	28
#define REALLOC_LTA_OLD_BLOCK_SIZE	24	 
#define REALLOC_LTA_ACTUAL_MMAP_PTR	20
#define REALLOC_LTA_NEW_BLOCK_SIZE	16
.globl	myrealloc
.ent 	myrealloc
myrealloc:
	.frame $fp, REALLOC_SS, ra
	.set  noreorder
   	.cpload  t9
   	.set  reorder

	subu	sp, sp, REALLOC_SS
	sw	ra, REALLOC_O_RA(sp)			
	sw	$fp, REALLOC_O_FP(sp)
	sw	gp, REALLOC_O_GP(sp)

	sw	a0, REALLOC_O_ARG(sp)  	# Guardo el primer argumento en stack frame del caller
	sw	a1, REALLOC_O_ARG+4(sp)	# Guardo segundo argumento en stack frame del caller		
	sw	a0, REALLOC_LTA_ACTUAL_MMAP_PTR(sp)  # Temporary: actual mmap(2) pointer.
	sw	a1, REALLOC_LTA_NEW_BLOCK_SIZE(sp) # Temporary: new block size	
	move	$fp, sp

	# Calculate the actual mmap(2) pointer.
	#
	lw	t0, REALLOC_O_ARG(sp)			
	subu	t0, t0, 8
	sw	t0, REALLOC_LTA_ACTUAL_MMAP_PTR(sp)		

	# XXX Sanity check: the argument pointer must be checked
	# in before we try to release the memory block.
	#
	# First, check the allocation signature.
	#
	lw	t0, REALLOC_LTA_ACTUAL_MMAP_PTR(sp) # t0: actual mmap(2) pointer.
	lw	t1, 0(t0)
	bne	t1, MYMALLOC_SIGNATURE, myrealloc_die

	# Second, check the memory block trailer.
	#
	lw	t0, REALLOC_LTA_ACTUAL_MMAP_PTR(sp) # t0: actual mmap(2) pointer. 	
	lw	t1, 4(t0)  # t1: actual mmap(2) block size.
	sw	t1, REALLOC_LTA_OLD_BLOCK_SIZE(sp)
	addu	t2, t0, t1 # t2: trailer pointer.
	lw	t3, -4(t2)
	xor	t3, t3, t1
	bne	t3, MYMALLOC_SIGNATURE, myrealloc_die

	lw	a0, REALLOC_LTA_NEW_BLOCK_SIZE(sp)	# cargo el argumento para el malloc
	la	t9, mymalloc
	jalr	t9					# llamo al malloc
	sw	v0, REALLOC_LTA_NEW_DATA_PTR(sp) 	#guardo el puntero del malloc
	beqz	v0, myrealloc_return			#si no se puede asignar salgo

	lw	t0, REALLOC_LTA_NEW_BLOCK_SIZE(sp)
	lw	t1, REALLOC_LTA_OLD_BLOCK_SIZE(sp)
	lw	a2, REALLOC_LTA_OLD_BLOCK_SIZE(sp)
	bgeu	t0, t1, seguir
	lw	a2, REALLOC_LTA_NEW_BLOCK_SIZE(sp)
seguir:	lw	a0, REALLOC_LTA_NEW_DATA_PTR(sp)
	lw	a1, REALLOC_O_ARG(sp)
	la	t9, mymemcpy
	jalr	t9

	lw	a0, REALLOC_O_ARG(sp)
	la	t9, myfree
	jalr	t9
	
	j	myrealloc_return

myrealloc_die:
	# Generate a segmentation faul by writing to the first
	# byte of the adress space (a.ka. the NULL pointer).
	#
	sw t0, 0(zero)

myrealloc_return:
	# Valor de retorno
	lw 	v0, REALLOC_LTA_NEW_DATA_PTR(sp)

	# Destruyo el stack frame
	#
	move sp, $fp
	lw	ra,  REALLOC_O_RA(sp)		
	lw	$fp, REALLOC_O_FP(sp)	
	addu	sp, sp, REALLOC_SS
	j	ra
.end	myrealloc
\end{Verbatim}
\end{scriptsize}

\begin{thebibliography}{99}

\bibitem{MIP96} MIPS RISC Processor Supplement, ``SYSTEM V APPLICATION BINARY INTERFACE Intel,'' 1996

\bibitem{MIP} ``MIPS ABI: Function Calling Convention,'' Organización de computadoras - 66.20

\bibitem{WIK} http://es.wikipedia.org/wiki/MIPS\_\%28procesador\%29

\end{thebibliography}


\end{document}
